package com.exercises;

import com.exercises.common.TreeNode;

import java.util.ArrayList;
import java.util.List;

public class Exercise879 {
    List<TreeNode> list = new ArrayList<>();

    public int official(int n, int minProfit, int[] group, int[] profit) {
        int[][] dp = new int[n + 1][minProfit + 1];
        for (int i = 0; i <= n; i++) {
            dp[i][0] = 1;
        }
        int len = group.length, MOD = (int) 1e9 + 7;
        for (int i = 1; i <= len; i++) {
            int members = group[i - 1], earn = profit[i - 1];
            for (int j = n; j >= members; j--) {
                for (int k = minProfit; k >= 0; k--) {
                    dp[j][k] = (dp[j][k] + dp[j - members][Math.max(0, k - earn)]) % MOD;
                }
            }
        }
        return dp[n][minProfit];
    }


    public int profitableSchemes(int n, int minProfit, int[] group, int[] profit) {
        int length = group.length;
        //dp[i][j] 表示i个人能够创造大于等于j的利润的组合数
        int[][] dp = new int[n + 1][minProfit + 1];
        for (int i = 0; i <= n; i++) {
            //所有人都不动,创造利润为0的数量为1
            dp[i][0] = 1;
        }
        int MOD = (int) 1e9 + 7;
        for (int i = 1; i <= length; i++) {
            int g = group[i - 1], p = profit[i - 1];
            //当前任务需要的人数g  创造的利润p
            for (int j = n; j > g; j--) {
                //如果选用了当前任务 人数的范围从g+1到n
                //如果不选用当前任务 人数范围不变 利润不变还是原来的dp[i][j]
                for (int k = minProfit; k >= 0; k--) {
                    dp[j][k] = (dp[j][k] + dp[j - g][Math.max(k - p, 0)]) % MOD;
                }
            }
        }
        return dp[n][minProfit];

    }
}
